Algorithms And Networks

• A2.10

  Algorithms and Networks

  Part II, 2001

  (i) Let $G$ be a directed network with nodes $N$ and $\operatorname{arcs} A$. Let $S \subset N$ be a subset of the nodes, $x$ be a flow on $G$, and $y$ be the divergence of $x$. Describe carefully what is meant by a cut $Q=[S, N \backslash S]$. Define the arc-cut incidence $e_{Q}$, and the flux of $x$ across $Q$. Define also the divergence $y(S)$ of $S$. Show that $y(S)=x \cdot e_{Q}$.

  Now suppose that capacity constraints are specified on each of the arcs. Define the upper cut capacity $c^{+}(Q)$ of $Q$. State the feasible distribution problem for a specified divergence $b$, and show that the problem only has a solution if $b(N)=0$ and $b(S) \leqslant c^{+}(Q)$ for all cuts $Q=[S, N \backslash S]$.

  (ii) Describe an algorithm to find a feasible distribution given a specified divergence $b$ and capacity constraints on each arc. Explain what happens when no feasible distribution exists.

  Illustrate the algorithm by either finding a feasible circulation, or demonstrating that one does not exist, in the network given below. Arcs are labelled with capacity constraint intervals.

  

  Part II

  comment

• A3.10

  Algorithms and Networks

  Part II, 2001

  (i) Let $P$ be the problem

  $$\text { minimize } f(x) \quad \text { subject to } h(x)=b, \quad x \in X \text {. }$$

  Explain carefully what it means for the problem $P$ to be Strong Lagrangian.

  Outline the main steps in a proof that a quadratic programming problem

  $$\operatorname{minimize} \frac{1}{2} x^{T} Q x+c^{T} x \quad \text { subject to } A x \geqslant b$$

  where $Q$ is a symmetric positive semi-definite matrix, is Strong Lagrangian.

  [You should carefully state the results you need, but should not prove them.]

  (ii) Consider the quadratic programming problem:

  $$\begin{aligned} \operatorname{minimize} & x_{1}^{2}+2 x_{1} x_{2}+2 x_{2}^{2}+x_{1}-4 x_{2} \\ \text { subject to } 3 x_{1}+2 x_{2} \leqslant 6, \quad x_{1}+x_{2} \geqslant 1 . \end{aligned}$$

  State necessary and sufficient conditions for $\left(x_{1}, x_{2}\right)$ to be optimal, and use the activeset algorithm (explaining your steps briefly) to solve the problem starting with initial condition $(2,0)$. Demonstrate that the solution you have found is optimal by showing that it satisfies the necessary and sufficient conditions stated previously.

  comment

• A4.11

  Algorithms and Networks

  Part II, 2001

  State the optimal distribution problem. Carefully describe the simplex-on-a-graph algorithm for solving optimal distribution problems when the flow in each arc in the network is constrained to lie in the interval $[0, \infty)$. Explain how the algorithm can be initialised if there is no obvious feasible solution with which to begin. Describe the adjustments that are needed for the algorithm to cope with more general capacity constraints $x(j) \in\left[c^{-}(j), c^{+}(j)\right]$ for each arc $j$ (where $c^{\pm}(j)$ may be finite or infinite).

  Part II

  comment

• A2.10

  Algorithms and Networks

  Part II, 2002

  (i) Let $G$ be a directed network with nodes $N$, arcs $A$ and capacities specified on each of the arcs. Define the terms feasible flow, divergence, cut, upper and lower cut capacities. Given two disjoint sets of nodes $N^{+}$and $N^{-}$, what does it mean to say that a cut $Q$ separates $N^{+}$from $N^{-}$? Prove that the flux of a feasible flow $x$ from $N^{+}$to $N^{-}$is bounded above by the upper capacity of $Q$, for any cut $Q$ separating $N^{+}$from $N^{-}$.

  (ii) Define the maximum-flow and minimum-cut problems. State the max-flow min-cut theorem and outline the main steps of the maximum-flow algorithm. Use the algorithm to find the maximum flow between the nodes 1 and 5 in a network whose node set is $\{1,2, \ldots, 5\}$, where the lower capacity of each arc is 0 and the upper capacity $c_{i j}$ of the directed arc joining node $i$ to node $j$ is given by the $(i, j)$-entry in the matrix

  $$\left(\begin{array}{ccccc} 0 & 7 & 9 & 8 & 0 \\ 0 & 0 & 6 & 8 & 4 \\ 0 & 9 & 0 & 2 & 10 \\ 0 & 3 & 7 & 0 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$$

  [The painted-network theorem can be used without proof but should be stated clearly. You may assume in your description of the maximum-flow algorithm that you are given an initial feasible flow.]

  comment

• A3.10

  Algorithms and Networks

  Part II, 2002

  (i) Consider the unconstrained geometric programme GP

  $$\text { minimise } g(t)=\sum_{i=1}^{n} c_{i} \prod_{j=1}^{m} t_{j}^{a_{i j}}$$

  subject to $t_{j}>0 \quad j=1, \ldots, m$.

  State the dual problem to GP. Give a careful statement of the AM-GM inequality, and use it to prove the primal-dual inequality for GP.

  (ii) Define min-path and max-tension problems. State and outline the proof of the max-tension min-path theorem.

  A company has branches in five cities $A, B, C, D$ and $E$. The fares for direct flights between these cities are as follows:

  \begin{tabular}{l|lllll} & $\mathrm{A}$ & $\mathrm{B}$ & $\mathrm{C}$ & $\mathrm{D}$ & $\mathrm{E}$ \ \hline $\mathrm{A}$ & $-$ & 50 & 40 & 25 & 10 \ $\mathrm{~B}$ & 50 & $-$ & 20 & 90 & 25 \ $\mathrm{C}$ & 40 & 20 & $-$ & 10 & 25 \ $\mathrm{D}$ & 25 & 90 & 10 & $-$ & 55 \ $\mathrm{E}$ & 10 & 25 & 25 & 55 & $-$ \end{tabular}

  Formulate this as a min-path problem. Illustrate the max-tension min-path algorithm by finding the cost of travelling by the cheapest routes between $D$ and each of the other cities.

  comment

• A4.11

  Algorithms and Networks

  Part II, 2002

  Write an essay on Strong Lagrangian problems. You should give an account of duality and how it relates to the Strong Lagrangian property. In particular, establish carefully the relationship between the Strong Lagrangian property and supporting hyperplanes.

  Also, give an example of a class of problems that are Strong Lagrangian. [You should explain carefully why your example has the Strong Lagrangian property.]

  comment

• A2.10

  Algorithms and Networks

  Part II, 2003

  (i) Consider a network with node set $N$ and set of directed arcs $A$ equipped with functions $d^{+}: A \rightarrow \mathbb{Z}$ and $d^{-}: A \rightarrow \mathbb{Z}$ with $d^{-} \leqslant d^{+}$. Given $u: N \rightarrow \mathbb{R}$ we define the differential $\Delta u: A \rightarrow \mathbb{R}$ by $\Delta u(j)=u\left(i^{\prime}\right)-u(i)$ for $j=\left(i, i^{\prime}\right) \in A$. We say that $\Delta u$ is a feasible differential if

  $$d^{-}(j) \leqslant \Delta u(j) \leqslant d^{+}(j) \text { for all } j \in A$$

  Write down a necessary and sufficient condition on $d^{+}, d^{-}$for the existence of a feasible differential and prove its necessity.

  Assuming Minty's Lemma, describe an algorithm to construct a feasible differential and outline how this algorithm establishes the sufficiency of the condition you have given.

  (ii) Let $E \subseteq S \times T$, where $S, T$ are finite sets. A matching in $E$ is a subset $M \subseteq E$ such that, for all $s, s^{\prime} \in S$ and $t, t^{\prime} \in T$,

  $$\begin{array}{lll} (s, t),\left(s^{\prime}, t\right) \in M & \text { implies } & s=s^{\prime} \\ (s, t),\left(s, t^{\prime}\right) \in M & \text { implies } & t=t^{\prime} \end{array}$$

  A matching $M$ is maximal if for any other matching $M^{\prime}$ with $M \subseteq M^{\prime}$ we must have $M=M^{\prime}$. Formulate the problem of finding a maximal matching in $E$ in terms of an optimal distribution problem on a suitably defined network, and hence in terms of a standard linear optimization problem.

  [You may assume that the optimal distribution subject to integer constraints is integervalued.]

  comment

• A3.10

  Algorithms and Networks

  Part II, 2003

  (i) Consider the problem

  $$\begin{aligned} \operatorname{minimize} & f(x) \\ \text { subject to } & h(x)=b, \quad x \in X, \end{aligned}$$

  where $f: \mathbb{R}^{n} \rightarrow \mathbb{R}, h: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, X \subseteq \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$. State and prove the Lagrangian sufficiency theorem.

  In each of the following cases, where $n=2, m=1$ and $X=\{(x, y): x, y \geqslant 0\}$, determine whether the Lagrangian sufficiency theorem can be applied to solve the problem:

  (ii) Consider the problem in $\mathbb{R}^{n}$

  $$\begin{aligned} \operatorname{minimize} & \frac{1}{2} x^{T} Q x+c^{T} x \\ \text { subject to } & A x=b \end{aligned}$$

  where $Q$ is a positive-definite symmetric $n \times n$ matrix, $A$ is an $m \times n$ matrix, $c \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$. Explain how to reduce this problem to the solution of simultaneous linear equations.

  Consider now the problem

  $$\begin{aligned} \operatorname{minimize} & \frac{1}{2} x^{T} Q x+c^{T} x \\ \text { subject to } & A x \geqslant b \end{aligned}$$

  Describe the active set method for its solution.

  Consider the problem

  $$\begin{aligned} \operatorname{minimize} &(x-a)^{2}+(y-b)^{2}+x y \\ \text { subject to } & 0 \leqslant x \leqslant 1 \text { and } 0 \leqslant y \leqslant 1 \end{aligned}$$

  where $a, b \in \mathbb{R}$. Draw a diagram partitioning the $(a, b)$-plane into regions according to which constraints are active at the minimum.

  $$\begin{aligned} & \text { (a) } \quad f(x, y)=-x, \quad h(x, y)=x^{2}+y^{2}, \quad b=1 \text {; } \\ & \text { (b) } \quad f(x, y)=e^{-x y}, \quad h(x)=x, \quad b=0 \text {. } \end{aligned}$$

  comment

• A4.11

  Algorithms and Networks

  Part II, 2003

  Define the optimal distribution problem. State what it means for a circuit $P$ to be flow-augmenting, and what it means for $P$ to be unbalanced. State the optimality theorem for flows. Describe the simplex-on-a-graph algorithm, giving a brief justification of its stopping rules.

  Consider the problem of finding, in the network shown below, a minimum-cost flow from $s$ to $t$ of value 2 . Here the circled numbers are the upper arc capacities, the lower arc capacities all being zero, and the uncircled numbers are costs. Apply the simplex-on-agraph algorithm to solve this problem, taking as initial flow the superposition of a unit flow along the path $s,(s, a), a,(a, t), t$ and a unit flow along the path $s,(s, a), a,(a, b), b,(b, t), t$.

  

  Part II 2003

  comment

• A2.10

  Algorithms and Networks

  Part II, 2004

  (i) Define the minimum path and the maximum tension problems for a network with span intervals specified for each arc. State without proof the connection between the two problems, and describe the Max Tension Min Path algorithm of solving them.

  (ii) Find the minimum path between nodes $\mathbf{S}$ and $\mathbf{S}^{\prime}$ in the network below. The span intervals are displayed alongside the arcs.

  

  Part II 2004

  comment

• A3.10

  Algorithms and Networks

  Part II, 2004

  (i) Consider the problem

  $$\begin{aligned} \text { minimise } & f(x) \\ \text { subject to } & g(x)=b, x \in X, \end{aligned}$$

  where $f: \mathbb{R}^{n} \longrightarrow \mathbb{R}, g: \mathbb{R}^{n} \longrightarrow \mathbb{R}^{m}, X \subseteq \mathbb{R}^{n}, x \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$. State the Lagrange Sufficiency Theorem for problem $(*)$. What is meant by saying that this problem is strong Lagrangian? How is this related to the Lagrange Sufficiency Theorem? Define a supporting hyperplane and state a condition guaranteeing that problem $(*)$ is strong Lagrangian.

  (ii) Define the terms flow, divergence, circulation, potential and differential for a network with nodes $N$ and $\operatorname{arcs} A$.

  State the feasible differential problem for a network with span intervals $D(j)=$ $\left[d^{-}(j), d^{+}(j)\right], j \in A .$

  State, without proof, the Feasible Differential Theorem.

  [You must carefully define all quantities used in your statements.]

  Show that the network below does not support a feasible differential.

  

  Part II 2004

  comment

• A4.11

  Algorithms and Networks

  Part II, 2004

  (i) Consider an unrestricted geometric programming problem

  $$\min g(t), \quad t=\left(t_{1}, \ldots, t_{m}\right)>0,$$

  where $g(t)$ is given by

  $$g(t)=\sum_{i=1}^{n} c_{i} t_{1}^{a_{i 1}} \ldots t_{m}^{a_{i m}}$$

  with $n \geq m$ and positive coefficients $c_{1} \ldots, c_{n}$. State the dual problem of $(*)$ and show that if $\lambda^{*}=\left(\lambda_{1}^{*}, \ldots, \lambda_{n}^{*}\right)$ is a dual optimum then any positive solution to the system

  $$t_{1}^{a_{i 1}} \ldots t_{m}^{a_{i m}}=\frac{1}{c_{i}} \lambda_{i}^{*} v\left(\lambda^{*}\right), \quad i=1, \ldots, n,$$

  gives an optimum for primal problem $(*)$. Here $v(\lambda)$ is the dual objective function.

  (ii) An amount of ore has to be moved from a pit in an open rectangular skip which is to be ordered from a supplier.

  The skip cost is $£ 36$ per $1 \mathrm{~m}^{2}$ for the bottom and two side walls and $£ 18$ per $1 \mathrm{~m}^{2}$ for the front and the back walls. The cost of loading ore into the skip is $£ 3$ per $1 \mathrm{~m}^{3}$, the cost of lifting is $£ 2$ per $1 \mathrm{~m}^{3}$, and the cost of unloading is $£ 1$ per $1 \mathrm{~m}^{3}$. The cost of moving an empty skip is negligible.

  Write down an unconstrained geometric programming problem for the optimal size (length, width, height) of skip minimizing the cost of moving $48 \mathrm{~m}^{3}$ of ore. By considering the dual problem, or otherwise, find the optimal cost and the optimal size of the skip.

  comment